﻿#define _CRT_SECURE_NO_WARNINGS 1
#include <stdio.h>
#include <assert.h>
#include <stdlib.h>
// 原题连接：https://leetcode.cn/problems/remove-nth-node-from-end-of-list/
/*
题目描述：
给你一个链表，删除链表的倒数第 n 个结点，并且返回链表的头结点。

示例 1：
输入：head = [1,2,3,4,5], n = 2
输出：[1,2,3,5]

示例 2：
输入：head = [1], n = 1
输出：[]

示例 3：
输入：head = [1,2], n = 1
输出：[1]
 

提示：
链表中结点的数目为 sz
1 <= sz <= 30
0 <= Node.val <= 100
1 <= n <= sz
 
进阶：你能尝试使用一趟扫描实现吗？
*/

// Definition for singly-linked list.
struct ListNode {
    int val;
    struct ListNode *next;
};

// 开始解题：
struct ListNode* removeNthFromEnd(struct ListNode* head, int n) {
    if (NULL == head) {
        return NULL;
    }
    struct ListNode* fast = head;
    struct ListNode* slow = head;
    while (--n) {
        if (NULL == fast) {
            return NULL;
        }
        fast = fast->next;
    }
    struct ListNode* pre = NULL; // 保存slow的前一个节点
    while (fast->next) {
        fast = fast->next;
        pre = slow;
        slow = slow->next;
    }
    if (NULL == pre) { // pre为NULL，说明待删除的节点为头节点
        head = slow->next;
        free(slow);
    }
    else {
        pre->next = slow->next;
        free(slow);
    }
    return head;
}
 